

public class Solution {
}

class Trie {
    // 是否存在某一个字符结尾的单词
    private boolean isExist;
    // 子节点
    private Trie[] children;

    public Trie() {
        this.isExist = false;
        this.children = new Trie[26];
    }

    /**
     * 往前缀树中插入单词
     *
     * @param word
     */
    public void insert(String word) {
        Trie root = this;
        // 构建前缀树，根据字符的先后顺序将每个字符插入对应的前缀树节点
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            int index = ch - 'a';
            if (root.children[index] == null) {
                // 子节点为null，则为其构建26个子节点
                root.children[index] = new Trie();
            }
            // 将指针移动到子节点，用于构建下一层子节点
            root = root.children[index];
        }
        // 将单词的最后一个节点的isExist表示为true，表示存在一个以该字符结尾的单词
        root.isExist = true;
    }

    /**
     * 查询是否存在一个完整的单词
     *
     * @param word
     * @return
     */
    public boolean search(String word) {
        Trie node = searchPrefix(word);
        // 前缀树中有一条路径包含word
        return node != null && node.isExist;
    }

    /**
     * 查询是否存在以该字符为前缀的单词
     *
     * @param prefix
     * @return
     */
    public boolean startsWith(String prefix) {
        return searchPrefix(prefix) != null;
    }

    /**
     * @param prefix
     * @return 非null表示该前缀的最后一个节点，null表示不存以该前缀起始的单词
     */
    public Trie searchPrefix(String prefix) {
        Trie root = this;
        // 遍历前缀树
        for (int i = 0; i < prefix.length(); i++) {
            char ch = prefix.charAt(i);
            int index = ch - 'a';
            if (root.children[index] == null) {
                // 子节点不存在，说明不存在以prefix为前缀的单词
                return null;
            }
            // 将指针移动到子节点，判断下一个字符是否存在
            root = root.children[index];
        }
        return root;
    }
}